#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/**
 * 单链表查找
 */

typedef int DataType;

typedef struct Node
{
    DataType data;     // 数据域
    struct Node *next; // 指针域
} Node, *LinkList;

// 初始化带头结点单链表
void InitList(LinkList *L)
{
    *L = (Node *)malloc(sizeof(Node));
    (*L)->next = NULL;
}
// 按位置查找节点 平均时间复杂度O(n)
Node *getNode(LinkList L, int i)
{
    if (i < 0)
    {
        return NULL;
    }
    Node *p = L;
    int j = 0;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }

    return p;
}
/**
 * 单链表后插操作,在p节点之后插入元素e,时间复杂度O(1)
 */
bool InsertNextNode(Node *p, DataType e)
{
    if (p == NULL)
    {
        return false;
    }
    Node *s = (Node *)malloc(sizeof(Node));
    if (s == NULL)
    {
        printf("分配内存失败\n");
        return false;
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
// 带头结点的单链表按照位序插入元素
bool insertListWithHead(LinkList *L, int i, DataType e)
{
    if (i < 1)
    {
        return false;
    }

    // Node *p = *L;
    // int j = 0;
    // while (p != NULL && j < i - 1)
    // {
    //     p = p->next;
    //     j++;
    // }

    Node *p = getNode(*L, i - 1); // 找到第i-1个节点

    // if (p == NULL)
    // {
    //     return false;
    // }

    // Node *s = (Node *)malloc(sizeof(Node));
    // s->data = e;
    // s->next = p->next;
    // p->next = s;
    return InsertNextNode(p, e); // 后插操作
}
// 按值查找节点
Node *locateData(LinkList L, DataType e)
{
    Node *p = L->next; // 从第一个节点开始查找
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;
}
// 求表长度
int listLength(LinkList L)
{
    int len = 0;
    Node *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}
// 打印单链表
void PrintList(LinkList L)
{
    Node *p = L;
    while (p != NULL)
    {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
}
int main()
{
    LinkList L1;
    InitList(&L1);
    // 测试插入函数
    insertListWithHead(&L1, 1, 100);
    insertListWithHead(&L1, 2, 200);
    insertListWithHead(&L1, 3, 300);
    insertListWithHead(&L1, 1, 1100);

    printf("带头结点的链表:\n");
    PrintList(L1->next);

    int i = 3; // 尝试查找一个不存在的节点
    Node *node = getNode(L1, i);
    if (node != NULL)
    {
        printf("找到的第 %d 个节点数值为 : %d\n", i, node->data);
    }
    else
    {
        printf("第 %d 个节点不存在 (NULL)\n", i);
    }

    int data = 200;
    Node *node2 = locateData(L1, data);
    if (node2 != NULL)
    {

        printf("查找值为:%d的节点的值为:%d\n", data, node2->data);
    }
    else
    {
        printf("查找值为:%d的节点未找到\n", data);
    }

    // 链表长度
    int length = listLength(L1);
    printf("单链表长度为: %d\n", length);

    return 0;
}
